package _2022.hot100._56_合并区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-14 11:17
 */
public class Solution {

    //优化
    public int[][] merge2(int[][] intervals){
        if(intervals.length==0){
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        List<int[]> merged=new ArrayList<>();
        for(int i=0;i<intervals.length;i++){
            int L=intervals[i][0],R=intervals[i][1];
            if(merged.size()==0||merged.get(merged.size()-1)[1]<L){
                merged.add(new int[]{L,R});
            }else{
                merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
    //9ms
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        int len = intervals.length;
        int[][] res = new int[len][2];
        res[0] = intervals[0];
        int m = 0;
        for (int i = 1; i < len; i++) {
            if (res[m][0] <= intervals[i][0] && intervals[i][0] <= res[m][1]) {
                res[m][0] = Math.min(res[m][0], intervals[i][0]);
                res[m][1] = Math.max(res[m][1], intervals[i][1]);
            } else {
                m++;
                res[m] = intervals[i];
            }
        }
        int[][] ans = new int[m + 1][2];
        System.arraycopy(res, 0, ans, 0, m + 1);
        return ans;
    }


    public static void main(String[] args) {
        Solution s = new Solution();
//        int[][] merge = s.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        int[][] merge = s.merge(new int[][]{{1, 4}, {4, 5}});
        for (int[] arr : merge) {
            System.out.print("[" + arr[0] + " " + arr[1] + "] ");
        }
    }
}
